# 商品库存管理(差分数组)
"""
前缀和
如何计算数组 a[i] 到 a[j] 这个区间内所有数字之和?
可以使用最简单的累加法, 但是复杂度为O(j-i)
也可以使用前缀和的方法来计算
1. 首先我们需要求出前缀和数组
    s[i] = a[i] + s[i - 1]
    如: a = [1,5,7,9,3,2] 的前缀和数组为 s = [1,6,13,22,25,27]
2. 计算区间和
    计算 a[2] 到 a[4] 这个区间的和即 a[2] + a[3] + a[4],  可使用 s[4] - s[1] 得到, 也就是用前5项的和减掉前2项的和
    所以求 a[l] 到 a[r] 之间的和, 可以使用前缀和数组 s[r] - s[l-1] 来计算

差分数组
差分数组解决在区间上进行多次增减的问题, 当需要对数组中某个区间进行大量更新时，差分数组可以显著降低更新操作的时间复杂度。
1. 求出差分数组
    d[i] = d[i] − a[i−1]
2. 还原元数组(前缀和)
    a[i] = d[1] + d[2] + ⋯ + d[i]
    这个过程也就是使用前缀和的方法 a[i] = a[i] + s[i-1]
    例如:
    a = [1,5,7,9,3,2]
    d = [1,4,2,2,-6,-1]
    还原数组 a, 也就是对 d 求前缀和数组
    a = s = [1,5,7,9,3,2]

3. 区间更新
    如果我们需要给区间 a[l] 到 a[r] 之间的所有元素增加 x, 只需要做一下操作:
    d[l] = d[l] + x
    d[r + 1] = d[r + 1] - x
    在 i < l 时, a[i] 的值不变
    在 L <= i <= R 时, a[i] 的值增加了x
    在 i > R 时, a[i] 的值
    例如: 我们想在 a[1] - a[3] 这个区间中每个元素加 1
    a = [1,5,7,9,3,2]
    d = [1,4,2,2,-6,-1]
    d_1 = [1,5,2,2,-7,-1]
    a_1 = [1,6,8,10,3,2]
    这样也就实现了在 a[1] - a[3] 这个区间中每个元素加 1 的操作
"""
from leetcode import test_function as tf


def get_unique_num(n, arr):
    """获得每个区间独有的子区间的个数"""
    res = []
    count = [0] * (n + 1)
    for x, y in arr:
        for i in range(x, y + 1):
            count[i] += 1

    # 计算没有被任何区间覆盖的元素的数量. 无论如何操作, 这些商品的数量都是0, 所以最后还要计算每个区间时要加上这个基数
    zero_count = 0
    for i in count[1:]:
        if i == 0:
            zero_count += 1

    # 统计每个区间只被覆盖了一次的元素
    for x, y in arr:
        cnt = 0
        for i in range(x, y + 1):  # 遍历每个区间
            if count[i] == 1:
                cnt += 1
        res.append(cnt + zero_count)

    return res


def get_unique_num_diff(n, arr):
    """
    使用前缀和 + 差分数组的方法
    """
    res = []
    # 求差分数组, 其中diff[0]为闲置元素, diff[1]=arr[0]
    diff = [0] * (n + 2)
    for x, y in arr:
        diff[x] += 1
        diff[y + 1] -= 1

    # 使用前缀和还原数组
    count = [0] * (n + 1)
    for i in range(n + 1):
        count[i] = count[i - 1] + diff[i]

    # 计算没有被任何区间覆盖的元素的数量. 这里要考虑count[0]为闲置元素
    zero_count = count[1:].count(0)

    # 统计每个区间只被覆盖了一次的元素
    for x, y in arr:
        res.append(count[x:y + 1].count(1) + zero_count)

    return res


if __name__ == '__main__':
    # n, m = map(int, input().split())  # n表示总的区间长度[1-n], m表示子区间的个数
    # inp = []
    # for i in range(m):
    #     inp.append(tuple(map(int, input().split())))

    # 输入
    arr = []
    with open("../../data/2024_d.in", "r") as file:
        n, m = map(int, file.readline().split())
        for i in range(m):
            arr.append(tuple(map(int, file.readline().split())))
    # 输出
    res = []
    with open("../../data/2024_d.out", "r") as file:
        line = file.readline()
        while line:
            res.append(int(line))
            line = file.readline()

    inp = [{"n": 5, "arr": [(1, 2), (4, 5), (1, 3)]},
           {"n": n, "arr": arr},
           ]
    out = [[0, 2, 1], res]
    tf(get_unique_num, inp, out)
    tf(get_unique_num_diff, inp, out)
